package com.salim.leetcode.$96;

import java.util.HashMap;
import java.util.List;

public class UniqueBinarySearchTrees {
    //F(i, n) = G(i-1) * G(n-i)
    //如果不加缓存会超时
    //还有一种dp做法 思路太难了
    //https://leetcode.com/problems/unique-binary-search-trees/discuss/31666/DP-Solution-in-6-lines-with-explanation.-F(i-n)-G(i-1)-*-G(n-i)
    public int numTrees(int n) {
        HashMap<String,Integer> buffer = new HashMap<>();
        return countTrees(1,n,buffer);
    }

    private int countTrees (int start, int end,HashMap<String,Integer> buffer) {
        if(buffer.containsKey(start+"|"+end)){
            return buffer.get(start+"|"+end);
        }

        if (start > end) {
            return 0;
        }
        int count = 0;

        for(int idx = start; idx <= end; idx++) {
            int leftCount = countTrees(start, idx - 1,buffer);
            int rightCount = countTrees(idx + 1, end,buffer);
            if(leftCount==0 && rightCount==0){
                count += 1;
            }else if(leftCount==0){
                count += rightCount;
            }else if(rightCount==0){
                count += leftCount;
            }else{
                count += leftCount*rightCount;
            }
        }
        buffer.put(start+"|"+end,count);
        return count;
    }
}
